#include <iostream>
#include <stack>
#include "tree_traversal.h"

void preorder_recursive(Node *n ) {
	if(n) {
		std::cout << n->key << ' ';
		preorder_recursive(n->left);
		preorder_recursive(n->right);
	}
}

void preorder_stack(Node * root) {
	std::stack<Node*> s;
	s.push(root);
	while(!s.empty()) {
		Node* n = s.top(); s.pop();
		std::cout << n->key << ' ';
		if (n->right)
			s.push(n->right);
		if(n->left)
			s.push(n->left);
	}
}

void preorder_parent(Node* root) {
	Node * curr = root;
	Node * prev = nullptr;
	while(curr) {
		if ( curr->parent == prev) { // go down
			prev = curr;
			std::cout << curr->key << ' ';
			if (curr->left)
				curr = curr->left;
			else if (curr->right)
				curr = curr->right;
			else
				curr = curr->parent;
		}
		else if (curr->left == prev) {
			prev = curr;
			if (curr->right)
				curr = curr->right;
			else 
				curr = curr->parent;
		}
		else if (curr->right == prev) {
			prev = curr;
			curr = curr->parent;
		}
		else {
			throw "Unreachable";
		}
	}
}